package main

import (
	"errors"
	"fmt"
)

const CONTENT string = "I love FishC.com!"

/**
优先队列结点
*/
type qNode struct {
	char                 string
	weight               int
	next, lChild, rChild *qNode
}

/**
优先队列表头
*/
type qHead struct {
	size  int
	first *qNode
}

var hfmMap = map[string]string{}

/**
获取队列头数据
*/
func (q *qHead) get() (char string, weight int, err error) {
	if q.first != nil {
		char = q.first.char
		weight = q.first.weight

	} else {
		err = errors.New("No data")
	}
	return
}

/**
获取队友头并移除
*/
func (q *qHead) getAndRemove() (node *qNode) {
	if q.first != nil {
		node = q.first
		q.first = q.first.next
		q.size--
	}
	return
}

/**
增加队列节点
*/
func (q *qHead) addNode(n *qNode) {
	fmt.Printf("add data: [%s,%d]\n", n.char, n.weight)
	pre, cur := q.first, q.first
	for cur != nil && cur.weight < n.weight {
		pre = cur
		cur = cur.next
	}
	if pre == cur {
		q.first = n
	} else {
		pre.next = n
	}
	n.next = cur
	q.size++
}

func (q *qHead) add(char string, weight int) {
	q.addNode(&qNode{char: char, weight: weight})
}

/**
打印队列
*/
func (q *qHead) print() {
	cur := q.first
	for cur != nil {
		fmt.Printf("[%s,%d]-->", cur.char, cur.weight)
		cur = cur.next
	}
	fmt.Println()
}

/**
创建哈夫曼树
*/
func (q *qHead) buildHfmTree() (t *qNode) {
	for q.size > 1 {
		nl := q.getAndRemove()
		nr := q.getAndRemove()
		node := &qNode{}
		node.weight = nl.weight + nr.weight
		node.lChild = nl
		node.rChild = nr
		q.addNode(node)
	}
	return q.first
}

/**
打印树结构
*/

func (t *qNode) print() {
	if t != nil {
		fmt.Printf("[%s,%d]-->", t.char, t.weight)
		t.lChild.print()
		t.rChild.print()
	}
}

/**
创建hfm编码树
*/
func (t *qNode) buildHfmMap(code string) {
	if t != nil {
		if t.char != "" {
			hfmMap[t.char] = code
		}
		t.lChild.buildHfmMap(code + "0")
		t.rChild.buildHfmMap(code + "1")
	}
}

/**
根据输入字符串构建优先队列
*/
func buildQueue(info string) (q *qHead) {
	chars := make(map[string]int)
	q = &qHead{}
	for _, c := range info {
		if count, ok := chars[string(c)]; ok {
			chars[string(c)] = count + 1
		} else {
			chars[string(c)] = 1
		}
	}

	for k, v := range chars {
		q.addNode(&qNode{char: k, weight: v})
	}
	return q
}

/**
编码字符串
*/
func encode(content string) (res string) {
	for _, c := range content {
		res = res + hfmMap[string(c)]
	}
	return
}

/**
解码字符串
*/
func (t *qNode) decode(content string) (res string) {
	node := t
	for _, v := range content {
		if node.char != "" {
			res = res + node.char
			node = t
		}
		if v == '0' {
			node = node.lChild
		} else {
			node = node.rChild
		}
	}
	res = res + node.char
	return
}

func main() {
	pq := &qHead{}
	pq.add("我", 4)
	pq.add("爱", 6)
	pq.add("你", 1)
	pq.add("是", 3)
	pq.print()
	c, w, _ := pq.get()
	fmt.Printf("队列头数据[%s,%d]\n", c, w)
	pq.print()
	n := pq.getAndRemove()
	fmt.Printf("队列头数据[%s,%d]\n", n.char, n.weight)
	pq.print()

	qs := buildQueue(CONTENT)
	qs.print()

	hfmTree := qs.buildHfmTree()
	fmt.Printf("\n 哈夫曼树 :")
	hfmTree.print()

	hfmTree.buildHfmMap("")
	fmt.Printf("\nhfmMap: %v", hfmMap)

	enContent := encode(CONTENT)
	fmt.Printf("\n encode content:%s.  lenght:%d", enContent, len(enContent))

	deContent := hfmTree.decode(enContent)
	fmt.Printf("\n deencode content:%s.  lenght:%d", deContent, len(deContent))

	deContent = hfmTree.decode("111111111")
	fmt.Printf("\n deencode content:%s.  lenght:%d", deContent, len(deContent))
}
